package com.sunny;

public class MergeSort {

    public static void main(String[] args) {

        MergeSort mergeSort = new MergeSort();
        int[] arr = {2,1,8,5,3,9,0,2};
        mergeSort.merge(arr, 0, arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }

    }


    public void merge(int[] arr, int s, int t){

        if(s >= t)
            return;

        int mid = (s+t)>>1;
        merge(arr, s, mid);
        merge(arr, mid+1, t);
        mergeCore(arr, s, mid, mid+1, t);

    }

    public void mergeCore(int[] arr, int s1, int t1, int s2, int t2){
        int[] tmp = new int[t2-s1+1];
        int i = s1;
        int j = s2;
        int k = 0;
        while (i<=t1 && j<=t2){
            if(arr[i] <= arr[j]){
                tmp[k++] = arr[i++];
            }else{
                tmp[k++] = arr[j++];
            }
        }
        while (i<=t1){
            tmp[k++] = arr[i++];
        }
        while (j<=t2){
            tmp[k++] = arr[j++];
        }
        for(int l=0;l<tmp.length;l++){
            arr[s1+l] = tmp[l];
        }
    }

}
